package lab2;

import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class Grafo {
	private List<No> nos = new ArrayList<No>();
	private List<Aresta> arestas = new ArrayList<Aresta>();

	public void setArestas(List<Aresta> arestas){
		
		this.arestas.addAll(arestas);
	}

	public List<Aresta> getArestas() {

		return arestas;

	}

	public void setNos(List<No> Nos) {
		
		this.nos.addAll(Nos);
	}

	public List<No> getNos() {
		
		return this.nos;
	}
	
	public void ordenarLista(List<No> lista){
		
		for (int i=lista.size()-2;i>=0;i--){
			
			for (int j=0;j<i;j++){
				
				if (lista.get(j).getDistancia() > lista.get(j+1).getDistancia()){
					
					Collections.swap(lista, j, j+1);
				}
			}
		}
	}
	public List<No> encontrarMenorCaminhoDijkstra(No v1, No v2){
		
		List<No> menorCaminho = new ArrayList<No>();
		No NoCaminho = new No ("caminho");
		No atual = new No ("atual");
		No vizinho = new No ("vizinho");
		List<No> fronteira = new ArrayList<No>();
		int NosNaoVisitados = this.nos.size();
		
		atual = v1;
		fronteira.add(atual);
		menorCaminho.add(atual);
		
		
		for (int i=0;i< this.nos.size();i++){
			
			if (this.nos.get(i).equals(v1)){
				
				this.nos.get(i).setDistancia(0);
			} else{
				
				this.nos.get(i).setDistancia(9999);
				
			}
			
		}
		
		while (NosNaoVisitados != 0){
			
			atual = fronteira.get(0);
			
			for (int i=0; i<atual.getArestas().size();i++){
				
				
				if (atual.getArestas().get(i).getNos().get(0).equals(atual)){
					
					vizinho = atual.getArestas().get(i).getNos().get(1);
				} else {
					
					vizinho = atual.getArestas().get(i).getNos().get(0);
				}
				
				vizinho.setPai(atual);
				
				if (vizinho.getDistancia() > (atual.getDistancia() + atual.getArestas().get(i).getPeso())){
					
					vizinho.setDistancia(atual.getDistancia() + atual.getArestas().get(i).getPeso());
					if (vizinho.equals(v2)){
						menorCaminho.clear();
						NoCaminho = vizinho;
						while (!NoCaminho.equals(atual)){
							
							menorCaminho.add(NoCaminho);
							NoCaminho = NoCaminho.getPai();
							
						}
						this.ordenarLista(menorCaminho);
					}
				}
				fronteira.add(vizinho);
				
			}
			
			atual.visitar();
			NosNaoVisitados--;
			fronteira.remove(atual);
			this.ordenarLista(fronteira);
		
		}
				
		return menorCaminho;
	}	
}


